#include "train.h"


// 可以看作两个集合 前半部分为大部堆 后半部分为小顶堆

class MedianFinder {
public:
    typedef pair<int, int>PII;
    set<PII> s1, s2;
    int tot;
    MedianFinder() {
        tot = 0;
    }

    void addNum(int num) {
        if (s1.size() == 0 || num < -s1.begin()->first) s1.insert(PII(-num, tot++));
        else s2.insert(PII(num, tot++)); 

        int n1 = (s1.size() + s2.size() + 1) / 2;

        if (s1.size() == n1) return; // s1.size() == s2.size() || s1.size() == s2.size() + 1
        if (s1.size() < n1)
        {
            s1.insert(PII(-s2.begin()->first, tot++));
            s2.erase(s2.begin());
        }
        else // s1.size() > s2.size() + 1
        {
            s2.insert(PII(-s1.begin()->first, tot++));
            s1.erase(s1.begin());
        }

    }

    double findMedian() {
        if ((s1.size() + s2.size()) % 2) return -s1.begin()->first;
        double a = -s1.begin()->first;
        double b = s2.begin()->first;
        return (a + b) / 2.0;
    }
};